#include "TABU.h"
#include "Operator.h"
#include <iostream>


/**
 *	Crea una lista tabu (LT)
 *	@param: Numero de ciudades.
 *	@return: Lista TABU.
 */
int** newLT(int size) {

	int** LT;
	LT = new int*[size];

	for (int i = 0; i < size; i++)
		LT[i] = new int[size];

	for (int i = 0; i < size; i++)
		for (int j = 0; j < size; j++)
			LT[i][j] = 0;

	return LT;
}
/**
 * Encuentra una vecindad para una solucion.
 * @param: una solucion y un grado de variacion.
 * @return: Un vector con los intercambios que
 *          construyen la vecindad.
 */

/* Ciudad mas cercana a la ciudad actual
 * @param:  ciudad actual
 * 		    Solucion actual
 * 		    lista de ciudades no visitadas
 * @return: ciudad mas cercana
 * */
int TABU::nearestNeighbor(int i, Solution *s, vector<int> noVisitados) {

	int j;
	float menor = FLT_MAX;
	int posMenor;

	for (j = 0; j < noVisitados.size(); j++) {

		if (i < noVisitados[j]) {
			if (s->C[i][noVisitados[j]] < menor) {
				menor = s->C[i][noVisitados[j]];
				posMenor = noVisitados[j];
			}
		} else if (i != noVisitados[j]) {
			if (s->C[noVisitados[j]][i] < menor) {
				menor = s->C[noVisitados[j]][i];
				posMenor = noVisitados[j];
			}
		}
	}

	return posMenor;
}

vector<int> findNeighborsVector(Solution *sact, int paso) {

	vector<int> vecinos;
	vector<int> visitados;

	int k;
	if (paso < 6) {
		for (int i = 0; i < sact->cityNumber; i += paso)
			visitados.push_back(i);
	}
	for (int i = 0; i < sact->cityNumber - paso; i += 1) {
		if (paso < 6) {
			k = TABU::nearestNeighbor(i, sact, visitados);
			if (k < sact->cityNumber) {
				vecinos.push_back(i);
				if (k > 0)
					vecinos.push_back(k - 1);
				else
					vecinos.push_back(k + 1);
			}
		} else {
			for (int j = i + paso; j < sact->cityNumber; j += paso * 2) {
				vecinos.push_back(i);
				vecinos.push_back(j);
			}
		}

	}
	return vecinos;
}

/**
 *	Dada una solucion inicial, busca un optimo
 *	aplicando la metaheuristica TABU con memoria
 *	a corto plazo.
 *	@param: Una solucion inicial.
 *	@return: Una solucion.
 */
Solution* TABU::TABUSearch(Solution* is, int maxIter, int maxNoMejora,
		int LTsize) {

	Solution *s = is->clone();
	Solution *sE = is->clone();

	srand(time(NULL));
	int paso = rand() % (s->cityNumber / 3 + 5);
	int numIt = 0;
	int noMejora = 0;

	int** LT = newLT(is->cityNumber);

	vector<int> neighbors = findNeighborsVector(s, s->cityNumber / 2);
//	vector<int*> neighbors2;

	while (!neighbors.empty() && numIt < maxIter && noMejora < maxNoMejora) {

		LT = s->bestSolution(neighbors, sE, LT, LTsize);


	//	neighbors2 = Operator::threeOptNeighborhood(s);


	/*	for (int var = 0; var < neighbors2.size(); ++var) {

			cout<< neighbors2[var][0]<<" "<< neighbors2[var][1]<<" //"<<endl;

		}
		cout<<"Fin ------TOpt"<<endl;	*/

		if (s->cityNumber > numIt)
			neighbors = findNeighborsVector(s, paso + numIt);

		else
			neighbors = findNeighborsVector(s, numIt / s->cityNumber);



		if (s->cost < sE->cost) {
			sE = s->clone();
			noMejora = 0;
		}
		numIt++;
		noMejora++;
	}

	for (int i = 0; i < is->cityNumber; i++)
		delete[] LT[i];

	delete[] LT;
	delete s;

	sE->numIter = numIt;

	return sE;
}

